/*
 * @lc app=leetcode.cn id=969 lang=javascript
 *
 * [969] 煎饼排序
 */

// @lc code=start
/**
 * @param {number[]} arr
 * @return {number[]}
 */
var pancakeSort = function (arr) {
  const reverse = (arr, n, index) => {
    let i = 0;
    let j = n - 1;
    while (i < j) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      index[arr[i]] = i;
      index[arr[j]] = j;
      i++;
      j--;
    }
    return;
  };
  const index = new Array(arr.length + 1).fill(-1);
  const result = [];
  // 保存排序数字对应的下标
  for (let i = 0; i < arr.length; i++) {
    index[arr[i]] = i;
  }

  for (let i = arr.length; i >= 1; i--) {
    // 如果下标和原数组的位置对应，不需要排序。
    // 比如：数字4就在下标3的位置，类似[3,2,1,4]
    if (index[i] === i - 1) continue;
    // 需要反转的数已经在第一位了，就不用反转了
    if (index[i] !== 0) {
      result.push(index[i] + 1);
      reverse(arr, index[i] + 1, index);
    }
    // 如果第一位是数字1了也不需要反转了
    if (i !== 1) {
      result.push(i);
      reverse(arr, i, index);
    }
  }

  return result;
};
// @lc code=end
